package com.mamingchao.basic.swardToOffer.two;

/**
 * 小虎去附近的商店买苹果,奸诈的商贩使用了捆绑交易,只提供6个每袋和8个
 * 每袋的包装包装不可拆分。可是小虎现在只想购买恰好n个苹果,小虎想购买尽
 * 量少的袋数方便携带。如果不能购买恰好n个苹果,小虎将不会购买。输入一个
 * 整数n,表示小虎想购买的个苹果,返回最小使用多少袋子。如果无论如何都不
 * 能正好装下,返回-1。
 */
public class XiaoHuBuyApple {

    /* 思路： 优先使用8个的包装，一定是购买袋子最少得方式，所以
     先判断 能不能整除8；如果可以整除，那除数即时最优解
     如果不能整除8，那就从能用最多的8到 0个8 按这个顺序尝试；尝试成功，即为最优解
     */

    /**
     *
     * @param packageNumOfEight 装8个苹果的袋子数量
     * @param packageNumOfEight 装8个苹果的袋子数量
     * @return 返回最少袋子数最优解；如果此方法不是最优解，返回-1
     */
    private static int getMinPackage(int packageNumOfEight, int n){
        if (packageNumOfEight < 0 || packageNumOfEight * 8  > n)
            return -1;

        int appleNumInBigPackage = 8 * packageNumOfEight;
        int appleNumInSmallPackage = n - appleNumInBigPackage;

        // 如果大袋子装完，剩下的能正好装进小袋子，则找到了最优解
        if (appleNumInSmallPackage % 6 == 0) {
            System.out.println("使用大袋子--" + packageNumOfEight +"使用小袋子--" + appleNumInSmallPackage/6);
            return packageNumOfEight + appleNumInSmallPackage/6;
        } else {
            return getMinPackage(packageNumOfEight -1,n);
        }
    }

    public static void main(String[] args) {
        final int  n = 70; // 共 买54个苹果

        if (n % 8 == 0 ){
            // 全部用 大袋子装，最优解
            System.out.println("最优解为-" + n/8);
        } else {
            int result = getMinPackage(n/8, n);
            System.out.println("最优解为-" + result);
        }
    }


}
